% PPI Presentation Template, By Wang Yuanxuan <zellux at gmail dot gmail>

\documentclass{beamer}
% \usetheme{Warsaw}
% \usetheme{Darmstadt}
\mode<presentation>
\usetheme{boxes}
\useoutertheme{smoothbars}
\useinnertheme[shadow=true]{rounded}
% \usecolortheme{orchid}
\usecolortheme{whale}
\usecolortheme{orchid}

\addfootbox{section in head/foot}{\tiny\quad\color{white}\insertshorttitle}
\addfootbox{frametitle}{\tiny\color{white}\hfill Parallel Processing Institute, Fudan University\hfill}
\addfootbox{section in head/foot}{\tiny\color{white}\hfill Slide
  \insertframenumber\ of \inserttotalframenumber\quad}

% Section outline at the beginning of each section
\AtBeginSection{
  \begin{frame}
   \frametitle{Outline}
    \tableofcontents[sectionstyle=show/hide,subsectionstyle=show/show/hide]{}
 \end{frame}
}

\usepackage{graphicx}

\title[Demand-based Flash Translation Layer]  % short title displayed in the bottom line
  {DFTL: A Flash Translation Layer Employing Demand-based Selective Caching of Page-level
    Address Mappings}
\author{Aayush Gupta \quad Youngjae Kim \quad Bhuvan Urgaonkar}
\institute{The Pennsylvania State University, University Park}
\date{ASPLOS 2009}

\begin{document}

\begin{frame}
  \titlepage{}
  \begin{center}
      Presented by Wang Yuanxuan
  \end{center}
\end{frame}

\begin{frame}
  \frametitle{Outline}
  \tableofcontents[hideallsubsections]
\end{frame}

\section{Introduction}

\subsection{Flash Memory}

\begin{frame}
  \frametitle{Advantages}
  \begin{itemize}
  \item Significantly cheaper than main memory
  \item Price-per-byte is falling
  \item Improve the performance of disk-bases systems via caching and buffering
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Defects}
  \begin{itemize}
  \item Not always superiors in performance to a disk (in sequential accesses)
  \item \textbf{Poor performance with random writes}
  \end{itemize}
\end{frame}

\subsection{The Flash Translation Layer}

\begin{frame}
  \begin{block}{FTL}
    Maintains a mapping table of virtual addresses from upper layers to
    physical addresses
  \end{block}
  \begin{problem}
    Erases are at a much coarser spatial granularity than pages
  \end{problem}
\end{frame}

\begin{frame}
  \frametitle{Out-of-Place Updates}
  \begin{enumerate}
  \item<1-> chooses an already erased page
  \item<2-> writes to it
  \item<3-> invalidates the previous version of page
  \item<4-> updates its mapping table
  \begin{problem}
    GC is needed
  \end{problem}
  \end{enumerate}
\end{frame}

\subsection{Contributions}

\begin{frame}
  \begin{itemize}
  \item<1-> DFTL
  \item<2-> FlashSim
  \item<3-> Evaluations of realistic enterprise-scale workloads
  \end{itemize}
\end{frame}

\section{Background}

\subsection{Basics of Flash Memory Technology}

\begin{frame}
  \frametitle{Flash Memory}
  \begin{block}{Granularity}
    \begin{itemize}
    \item Blocks
    \item Pages
    \end{itemize}
  \end{block}

  \begin{block}{Out-of-Band Area}
    \begin{itemize}
    \item Error Correctness Code
    \item Logical page number
    \item State
      \begin{enumerate}
      \item valid
      \item invalid
      \item free/erased
      \end{enumerate}
    \end{itemize}
  \end{block}
\end{frame}

% table example
\begin{frame}
  \frametitle{NAND Flash Organization and Access Time Comparation}
  \begin{small}
    \setlength{\tabcolsep}{2pt}
    \begin{tabular}{|c|c|c|c|c|c|c|}
      \hline
      & \multicolumn{3}{|c|}{Data Unit Size} & \multicolumn{3}{|c|}{Access Time} \\ \cline{2-4} \cline{5-7}
      Flash Type & \multicolumn{2}{|c|}{Page(Bytes)} & Block & Page & Page & Block \\ \cline{2-3}
      & Data & OOB & (Bytes) & READ (us) & WRITE (us) & ERASE (\textbf{ms}) \\
      \hline \hline
      Small Block & 512 & 16 & (16K+512) & 41.75 & 226.75 & 2 \\ \hline
      Large Block & 2048 & 64 & (128K+4K) & 130.9 & 405.9 & 2 \\ \hline
    \end{tabular}
  \end{small}

  \begin{block}{Other considerations}
    \begin{itemize}
    \item wear-leveling
    \end{itemize}
  \end{block}
\end{frame}

\subsection{Flash Translation Layer}

\begin{frame}
  \frametitle{Two extremes}
  \begin{block}{Granularity}
    \begin{itemize}
    \item<1-> Page-level
      \begin{itemize}
      \item Fully associative cache
      \item Compact and efficient utilization
      \item Requires a large mapping table (32MB for 16GB)
      \end{itemize}
    \item<2-> Block-level
      \begin{itemize}
      \item Set-associative cache
      \item Reduce the size of the mapping table
      \item LPN offset within the block is fixed
      \item A grow in GC overhead
      \end{itemize}
    \end{itemize}
  \end{block}
\end{frame}

\begin{frame}
  \frametitle{Hybrid FTL Scheme}
  \begin{overprint}
    \onslide<1>
    \begin{itemize}
    \item Two groups of blocks
      \begin{itemize}
      \item Data Blocks: block-level
      \item Log/Update Blocks: page-level
      \end{itemize}
    \item Any update on the data blocks are performed by writes to the log blocks
    \end{itemize}
  \end{overprint}
\end{frame}

\begin{frame}
  \frametitle{Hybrid FTL Scheme}
  \includegraphics[width=\textwidth]{hybrid.jpg}
\end{frame}

\begin{frame}
  \frametitle{GC in Hybrid FTLs}
  \begin{overprint}
    \onslide<1>    
    \begin{block}{Various Merge Operations}
      \includegraphics[width=\textwidth]{merge-ops.jpg}
    \end{block}
    \onslide<2>
    \begin{block}{Expensive Full Merge}
      \includegraphics[width=\textwidth]{full-merge.jpg}
    \end{block}
  \end{overprint}
\end{frame}

\section{Design of DFTL}

\subsection{DFTL Architecture}

\begin{frame}
  \begin{block}{Contention}
    Doing away with log-blocks!
  \end{block}

  \begin{block}{Features}
    \begin{itemize}
    \item Making use of temporal locality
    \item Page-based mapping table on the flash device
    \item Data area to store the image (2MB for 1GB)
    \end{itemize}
  \end{block}
\end{frame}

\begin{frame}
  \frametitle{Data Pages and Tranlation Pages}
  \includegraphics[width=\textwidth]{pages.jpg}
\end{frame}

\subsection{Logical to Physical Address Translation}

\begin{frame}
  \frametitle{Algorithm}
  \begin{overprint}
    \onslide<1>
    \includegraphics[height=.8\textheight]{algorithm.jpg}
    \onslide<2>
    \includegraphics[width=\textwidth]{algo-example.jpg}  
  \end{overprint}
\end{frame}

\begin{frame}
  \frametitle{Overhead}
  \begin{itemize}
  \item Worst-case: 2 translation page reads and 1 translation page write
  \item Rooted deeply in temporal locality
  \item Batch updates optimization
  \end{itemize}
\end{frame}

\subsection{R/W Operations and GC}

\begin{frame}
  \begin{itemize}
  \item Current Data/Tranlation Block for writing
  \item Invoke GC when $GC_{threadhold}$ is crossed
  \end{itemize}
\end{frame}

\section{The FlashSim Simulator}

\subsection{FlashSim}

\begin{frame}
  \begin{itemize}
  \item Built by enhancing Disksim
  \item Able to simulate different storage sub-system components
  \item Core FTL engine
  \end{itemize}
\end{frame}

\section{Experimental Results}

\subsection{Setup}

\begin{frame}
  \frametitle{Evaluation Setup}
  \begin{tabular}{|c|c|c|c|c|}
    \hline{}
    Workloads & Avg. Req. & Read & Seq. & Inter-arrival \\
     & Size (KB) & (\%) & (\%) & Time (ms) \\ \hline \hline
    Financial [25] & 4.38 & 9.0 & 2.0 & 133.50 \\ \hline
    Cello99 [10] & 5.03 & 35.0 & 1.0 & 41.01 \\ \hline
    TPC-H [28] & 12.82 & 95.0 & 18.0 & 155.56 \\ \hline
    Web Search [26] & 14.86 & 99.0 & 14.0 & 9.97 \\ \hline
  \end{tabular}
  Baseline: Pure page-based FTL
\end{frame}

\subsection{Results}

\begin{frame}
  \frametitle{Average System Response Time}
  \begin{overprint}
    \onslide<1>
    \includegraphics[width=.7\textwidth]{response.jpg}
    \onslide<2>
    \includegraphics[width=\textwidth]{rate-perf.jpg}
  \end{overprint}
\end{frame}

\section{Concluding Remarks}

\begin{frame}
  \frametitle{DFTL Offers}
  \begin{itemize}
  \item improved performance
  \item reduced GC overhead
  \item improved overload behavior
  \item free from any tunnable parameters
  \end{itemize}
\end{frame}

\begin{frame}
  \begin{center}
    \frametitle{Q \& A}
  \end{center}
\end{frame}

\end{document}
